/*
 * Copyright © 2021 http://www.hn-szzy.com/ All rights reserved.
 */
package com.xjh.basestudy.leetcode.understand.linkedlist;


import org.junit.Test;


/**
 * @author： 徐建华
 * @date： 2022/3/18
 * @description：
 */
public class TestListNode {
    public ListNode head;// 链表的头

    /**
     * 1.创建链表的几种方式
     */
    @Test
    public void createListNode() {
        /**方式一：枚举创建多个节点并连接*/
        creatList();

        /**方式二：头插法*/
        addFirst(99);

        /**方式三：尾插法*/
        addLast(66);
        // 获取链表长度
        System.out.println("获取链表长度==="+size());
        // 移除值为xx的某节点
        remove(11);
        // 清空链表
        clear();
    }

    /**
     * 2.链表遍历
     * 我们可以知道，节点与节点之间通过next产生联系。并且我们已将创建了head，即头节点的地址，通过head的移动来实现链表的打印。
     * 注意：为了使head一直存在且有意义，我们在display()函数中定义一个cur：ListNode cur = this.head;来替代head。
     * 对于head的移动，可用head = head.next来实现。
     */
    @Test
    public void display() {
        // 创建一个链表
        creatList();
        // 定义一个指针
        ListNode cur = this.head;
        // 指针一直往后移动，直到为null
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    /**
     * 3.获取链表长度
     */

    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //找到key的前驱（前一节点）
    public ListNode searchPrev(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null){
            return;
        }
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if(cur == null){
            return;             //没有要删除的节点
        }
        ListNode del = cur.next;//定义要删除的节点
        cur.next = del.next;
    }
/**
 *
 * 清空链表
 * 1.简单粗暴的方法：将头节点置为空head = null；即可
 *
 * 2.细腻温柔的做法：将每一个节点都置为空
 *
 *
 * */
    public void clear(){
        while(this.head != null){
            ListNode curNext = this.head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }



    @Test
    public void test01() {
        // 创建链表l1
        // 创建一个节点并输入数据
        ListNode l1 = new ListNode(1);
        // 为该节点续上一个节点，并输入数据
        l1.next = new ListNode(3);
        // 创建链表l2
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        // 合并链表
        ListNode head = mergeTwoLists(l1, l2);
        /**
         * （1）带傀儡节点的链表遍历（直接指向第一个的下一个（head.next，所以没有第一个数据））
         * head会指向一个单独的傀儡结点（head中存放的是傀儡结点的地址），傀儡结点的next指向a
         * int i=0 i<2 i++;
         * */
        for (ListNode cur = head.next; cur != null; cur = cur.next) {
            System.out.println("带傀儡节点的链表遍历===" + cur.val);

        }
        System.out.println("第一个节点数据===" + head.val);
        System.out.println("第二个节点数据===" + head.next.val);
        /**
         * （2）不带傀儡结点的链表
         * 循环原理，让变量不断指向下一个节点的地址、直到变量指向为空为止
         * */
        for (ListNode cur = head; cur != null; cur = cur.next) {
            System.out.println("不带傀儡节点的链表遍历===" + cur.val);
        }
        head = head.next.next;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            System.out.println("tt===" + cur.val);
        }

        /*通过遍历，找到链表的最后一个结点（原理：把变量的值赋值给最后一个节点）*/
        // ListNode cur = head;
        // while (cur.next != null) {
        //    cur = cur.next;
        //}
        // System.out.println(cur.val);

        /*通过遍历，找到链表的倒数第二个结点*/
        // ListNode cur = head;
        ////要保证当前链表不为空，且cur.next不为空，否则进行解引用时会报错
        // while (cur != null && cur.next != null && cur.next.next != null) {
        //    cur = cur.next;
        //}
        // System.out.println(cur.val);

        /*遍历链表，找到链表的第N个结点*/
        // 取链表的第N个结点，假设N=3
        // int N = 3;
        ////创建一个cur引用指向头节点
        // ListNode cur = head;
        // for (int i = 1; i < N; i++) {
        //    cur = cur.next;
        //}
        // System.out.println(cur.val);
        /*计算链表中元素的个数*/
        // int n = 0;
        // for (ListNode cur = head; cur != null; cur = cur.next) {
        //    n++;
        //}
        // System.out.println(n);
        /*遍历链表，找到链表的倒数第N个结点*/
        // 假设要找链表中倒数第三个结点
        // int N = 3;
        // ListNode cur = head;
        ////根据规律可得：倒数第N个结点即整数第n+1-N个结点
        // for (int i = 1; i < n + 1 - N; i++) {
        //    cur = cur.next;
        //}
        // System.out.println(cur.val);

        /*通过遍历，找到链表上是否存在某个元素*/
        // 假设所找的元素为5
        // int n = 5;
        // ListNode cur = head;
        // for (; cur != null; cur = cur.next) {
        //    if (cur.val == n) {
        //        break;
        //    }
        //}
        // if (cur != null) {
        //    System.out.println("存在");
        //} else {
        //    System.out.println("不存在");
        //}

    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public void creatList() {
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);

        // 为什么把listNode1赋值给head，然后改变listNode1,head也会变
        // 将第一个节点赋值给头节点（将头节点指向第一个节点），然后给节点按顺序连接
        this.head = listNode1;

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;


    }

    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        // 把头节点放到新建节点的指针域
        node.next = this.head;
        // 然后把新建节点赋值给头节点（让头节点指向新建节点）
        this.head = node;
    }

    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (this.head == null) {
            this.head = node;
        } else {
            // 创建一个指针
            ListNode cur = this.head;
            // 把指针指向最后一个节点
            while (cur.next != null) {
                cur = cur.next;
            }
            // 此时最后一个节点指针域为null，改成指向新建节点即可
            cur.next = node;
        }
    }


}
